from typing import *


class Solution:
    def countPairsOfConnectableServers(
        self, edges: List[List[int]], signalSpeed: int
    ) -> List[int]:
        n = len(edges) + 1
        next = [[] for _ in range(n)]
        ws = [[0] * n for _ in range(n)]

        for a, b, w in edges:
            next[a].append(b)
            next[b].append(a)
            ws[a][b] = w
            ws[b][a] = w
        ans = [0] * n

        def q(a, b, val):
            val += ws[a][b]
            tot = 1 if val % signalSpeed == 0 else 0
            for nxt in next[b]:
                if nxt != a:
                    tot += q(b, nxt, val % signalSpeed)
            return tot

        def f(node):
            p = [0] * len(next[node])
            for i in range(len(p)):
                nxt = next[node][i]
                p[i] = q(node, nxt, 0)
            tot = sum(p)
            ans = 0
            for v in p:
                ans += v * (tot - v)
            return ans

        for i in range(n):
            ans[i] = f(i) // 2
        return ans


s = Solution()
print(
    s.countPairsOfConnectableServers(
        [[0, 1, 1], [1, 2, 5], [2, 3, 13], [3, 4, 9], [4, 5, 2]], 1
    )
)
